//给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。
// 请你找出并返回这两个正序数组的 中位数 。
//
// 
//
// 示例 1： 
//
// 
//输入：nums1 = [1,3], nums2 = [2]
//输出：2.00000
//解释：合并数组 = [1,2,3] ，中位数 2
// 
//
// 示例 2： 
//
// 
//输入：nums1 = [1,2], nums2 = [3,4]
//输出：2.50000
//解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
// 
//
// 示例 3： 
//
// 
//输入：nums1 = [0,0], nums2 = [0,0]
//输出：0.00000
// 
//
// 示例 4： 
//
// 
//输入：nums1 = [], nums2 = [1]
//输出：1.00000
// 
//
// 示例 5： 
//
// 
//输入：nums1 = [2], nums2 = []
//输出：2.00000
// 
//
// 
//
// 提示： 
//
// 
// nums1.length == m 
// nums2.length == n 
// 0 <= m <= 1000 
// 0 <= n <= 1000 
// 1 <= m + n <= 2000 
// -106 <= nums1[i], nums2[i] <= 106 
// 
//
// 
//
// 进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？ 
// Related Topics 数组 二分查找 分治 
// 👍 4322 👎 0


package service.exercise.hard.leetcode.editor.cn;

//Java：寻找两个正序数组的中位数
public class P4MedianOfTwoSortedArrays {
    public static void main(String[] args) {
        Solution solution = new P4MedianOfTwoSortedArrays().new Solution();
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 寻找两个数组的中位数
         *
         * @param nums1
         * @param nums2
         * @return
         */
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            int size = nums1.length + nums2.length;
            boolean even = (size & 1) == 0;
            if (nums1.length != 0 && nums2.length != 0) {
                if (even) {
                    return (findKthNum(nums1, nums2, size / 2) + findKthNum(nums1, nums2, size / 2 + 1)) / 2D;
                } else {
                    return findKthNum(nums1, nums2, (size / 2) + 1);
                }
            } else if (nums1.length != 0) {
                if (even) {
                    return (nums1[(size - 1) / 2] + nums1[size / 2]) / 2D;
                } else {
                    return nums1[size / 2];
                }
            } else if (nums2.length != 0) {
                if (even) {
                    return (nums2[(size - 1) / 2] + nums2[size/2]) / 2D;
                } else {
                    return nums2[size / 2];
                }
            }
            return 0.0;
        }

        private int findKthNum(int[] arr1, int[] arr2, int kth) {
            int[] longs = arr1.length >= arr2.length ? arr1 : arr2;
            int[] shorts = arr1.length < arr2.length ? arr1 : arr2;
            int l = longs.length;
            int s = shorts.length;
            if (kth <= s) {
                return getUpMedian(shorts, 0, kth - 1, longs, 0, kth - 1);
            }
            if (kth > l) {
                if (shorts[kth - l - 1] >= longs[l - 1]) {
                    return shorts[kth - l - 1];
                }
                if (longs[kth - s - 1] >= shorts[s - 1]) {
                    return longs[kth - s - 1];
                }
                return getUpMedian(shorts, kth - l, s - 1, longs, kth - s, l - 1);
            }
            //第二段
            if (longs[kth - s - 1] >= shorts[s - 1]) {
                return longs[kth - s - 1];
            }
            return getUpMedian(shorts, 0, s - 1, longs, kth - s, kth - 1);
        }

        private int getUpMedian(int[] A, int s1, int e1, int[] B, int s2, int e2) {
            int mid1 = 0;
            int mid2 = 0;
            while (s1 < e1) {
                mid1 = (s1 + e1) / 2;
                mid2 = (s2 + e2) / 2;
                // 刚好是中位数
                if (A[mid1] == B[mid2]) {
                    return A[mid1];
                }
                //奇数
                if (((e1 - s1 + 1) & 1) == 1) {
                    //剔除一个 谁大取谁
                    if (A[mid1] > B[mid2]) {
                        if (B[mid2] >= A[mid1 - 1]) {
                            return B[mid2];
                        }
                        e1 = mid1 - 1;
                        s2 = mid2 + 1;
                    } else {
                        //A[mid1] <B[mid2]
                        if (A[mid1] >= B[mid2 - 1]) {
                            return A[mid1];
                        }
                        e2 = mid2 - 1;
                        s1 = mid1 + 1;
                    }
                } else {
                    //偶数长度
                    if (A[mid1] > B[mid2]) {
                        e1 = mid1;
                        s2 = mid2 + 1;
                    } else {
                        e2 = mid2;
                        s1 = mid1 + 1;
                    }
                }

            }
            return Math.min(A[s1], B[s2]);
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}